package Q61;

import java.util.ArrayList;
import java.util.List;

/**
 * 旋转链表
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 *
 * @author 23737
 * @time 2021.11.05
 */
public class Test {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        ListNode l5 = new ListNode(5);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        ListNode listNode = new Solution().rotateRight(l1, 2);
        System.out.println(listNode.val);
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    ListNode(int x, ListNode next) {
        val = x;
        this.next = next;
    }
}

class Solution {
    // 计算链表的长度，并获取
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        List<ListNode> list = new ArrayList<>();
        // 迭代将节点添加到集合中
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        // 需要移动的距离
        k = k % list.size();
        if (k == 0) {
            return list.get(0);
        }
        // 计算移动后头节点的index
        k = list.size() - k;

        // 最后一个节点指向第一个节点
        list.get(list.size() - 1).next = list.get(0);
        // 断开链表
        list.get(k - 1).next = null;
        return list.get(k);
    }
    public ListNode rotateRight1(ListNode head, int k) {
        if(head == null || head.next == null)    return head;
        ListNode res = head, pre = head, head1 = head;
        int len = 0;
        while(head != null){
            len++;
            head = head.next;
        }
        k %= len;
        if(k == 0)  return res;
        while(k-- > 0){
            res = res.next;
        }
        while(res.next != null){
            res = res.next;
            pre = pre.next;
        }
        ListNode temp = pre.next;
        pre.next = null;
        res.next = head1;
        return temp;
    }
}
